package stack;

import java.util.Stack;

public class leetcode42接雨水 {
    // 双指针 时间O(n), 空间O(1)
    public int trap(int[] height) {
        int length = height.length;
        int left = 0;
        int right = length - 1;
        int i = 0;
        int j = length - 1;
        int sum = 0;
        while (left < right) {
            if (height[left] <= height[right]) {
                while (i < j && height[i] <= height[left]) {
                    sum += height[left] - height[i];
                    i++;
                }
                left = i;
            } else {
                while (i < j && height[j] <= height[right]) {
                    sum += height[right] - height[j];
                    j--;
                }
                right = j;
            }
        }
        return sum;
    }

    // 栈，栈底到栈顶从大到小，遇到比栈顶大的计算雨水
    public int trap1(int[] height) {
        int length = height.length;
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                Integer sec = stack.peek();
                sum += (i - sec - 1) * (Integer.min(height[i], height[sec]) - height[top]);
            }
            stack.push(i);
        }
        return sum;
    }
}
